home *** CD-ROM | disk | FTP | other *** search
/ ASME's Mechanical Engine…ing Toolkit 1997 December / ASME's Mechanical Engineering Toolkit 1997 December.iso / c_lang / ttt.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-26  |  12.0 KB  |  478 lines
  1. /*   This program simulates a constraint satisfaction
  2.      neural network for choosing tic-tac-toe moves as
  3.      described in Volume 2 of the PDP books.  The
  4.      network is presented a description of the board
  5.      and chooses the best move subject to predefined
  6.      constraints.
  7.  
  8.      It requires an EGA or CGA to display a Hinton diagram 
  9.      of the element activation levels.
  10.  
  11.      Author   : Gary Andriotakis
  12.      Compiler : Microsoft Quick C
  13.      Date     : 5 January 1989
  14. */
  15. #include<stdio.h>
  16. #include <stdio.h>
  17. #include <time.h>
  18. #include <graph.h>
  19. #define N 67
  20. #define GAIN 0.1
  21. #define SCALE 1.0/16.0
  22. static float w[N][N], bias[N], a[N], e[N];
  23. main()
  24. {
  25.    int j,mark = -1,converged;
  26.    time_t t;
  27. #ifdef DEBUG
  28.    initialize(a,w,bias);
  29. #endif
  30. #ifndef DEBUG
  31.    if(!_setvideomode(_ERESCOLOR))
  32.    {   printf("EGA required\n");
  33.        exit(0);
  34.    }
  35.    srand((int)time(&t));
  36.    drawboard();
  37.    do
  38.    {
  39.       putmarkers(&e[9],mark);
  40.       initialize();
  41.       boxes(a,N);
  42.       do
  43.       {  j = randint(N);
  44.          update(j);
  45.          boxes(a,j);
  46.          converged = ((j < 9) && (a[j] > 0.9));
  47.       } while(!converged && !kbhit());
  48.       if(converged)
  49.          mark = j;
  50.       else
  51.          mark = -1;
  52.    } while(converged || (kbhit() && getch() != 27));
  53.    _displaycursor(_GCURSORON);
  54.    _setvideomode(_DEFAULTMODE);
  55. #endif
  56. }
  57.  
  58. update(j)
  59. int j;
  60. {  int i;
  61.    float net;
  62.  
  63.    net = 0.0;
  64.    for(i = 0; i < N; i++)
  65.       net += w[i][j]*a[i];
  66.    net += bias[j];
  67.    net *= GAIN;
  68.    net += e[j];
  69.    if(net > 0.0)
  70.       a[j] += net*(1.0 - a[j]);
  71.    else
  72.       a[j] += net*a[j];
  73. }
  74.  
  75. initialize()
  76. {  int i,j;
  77. /*  initialize to zero */
  78.    for(i = 0; i < N; i++)
  79.    {  a[i] = 0.0;
  80.       bias[i] = 0.0;
  81.       for(j = 0; j < N; j++)
  82.          w[i][j] = 0.0;
  83.    }
  84.  
  85.    for(i = 0; i < 9; i++)
  86.    {  /* inhibit responses from occupied squares */
  87.       w[i+9][i] = -8.0;
  88.       w[i+18][i] = -8.0;
  89.       /*  mutual inhibition to insure only one response */
  90.       for(j = 0; j < 9; j++)
  91.          w[i][j] = -2.;
  92.       /*  self excitation to excourage self growth */
  93.       w[i][i] = 2.;
  94.    }
  95. /*  empty line detectors */
  96.    for(i = 0; i < 3; i++)
  97.    {  w[i+9][27] = -1.0;
  98.       w[i+18][27] = -1.0;
  99.       w[27][i] = 1.0;
  100.       w[i+12][28] = -1.0;
  101.       w[i+21][28] = -1.0;
  102.       w[28][i+3] = 1.0;
  103.       w[i+15][29] = -1.0;
  104.       w[i+24][29] = -1.0;
  105.       w[29][i+6] = 1.0;
  106.       w[9+4*i][30] = -1.0;
  107.       w[18+4*i][30] = -1.0;
  108.       w[30][4*i] = 1.0;
  109.       w[11+2*i][31] = -1.0;
  110.       w[20+2*i][31] = -1.0;
  111.       w[31][2+2*i] = 1.0;
  112.       w[9+3*i][32] = -1.0;
  113.       w[18+3*i][32] = -1.0;
  114.       w[32][3*i] = 1.0;
  115.       w[10+3*i][33] = -1.0;
  116.       w[19+3*i][33] = -1.0;
  117.       w[33][1+3*i] = 1.0;
  118.       w[11+3*i][34] = -1.0;
  119.       w[20+3*i][34] = -1.0;
  120.       w[34][2+3*i] = 1.0;
  121.    }
  122. /*   friendly doubleton detectors */
  123.    for(i = 0; i < 3; i++)
  124.    {  w[i+9][35] = 1.0;
  125.       w[i+18][35] = -2.0;
  126.       w[35][i] = 5.0;
  127.       w[i+12][36] = 1.0;
  128.       w[i+21][36] = -2.0;
  129.       w[36][i+3] = 5.0;
  130.       w[i+15][37] = 1.0;
  131.       w[i+24][37] = -2.0;
  132.       w[37][i+6] = 5.0;
  133.       w[9+4*i][38] = 1.0;
  134.       w[18+4*i][38] = -2.0;
  135.       w[38][4*i] = 5.0;
  136.       w[11+2*i][39] = 1.0;
  137.       w[20+2*i][39] = -2.0;
  138.       w[39][2+2*i] = 5.0;
  139.       w[9+3*i][40] = 1.0;
  140.       w[18+3*i][40] = -2.0;
  141.       w[40][3*i] = 5.0;
  142.       w[10+3*i][41] = 1.0;
  143.       w[19+3*i][41] = -2.0;
  144.       w[41][1+3*i] = 5.0;
  145.       w[11+3*i][42] = 1.0;
  146.       w[20+3*i][42] = -2.0;
  147.       w[42][2+3*i] = 5.0;
  148.    }
  149. /*   enemy doubleton detectors */
  150.    for(i = 0; i < 3; i++)
  151.    {  w[i+9][43] = -2.0;
  152.       w[i+18][43] = 1.0;
  153.       w[43][i] = 1.0;
  154.       w[i+12][44] = -2.0;
  155.       w[i+21][44] = 1.0;
  156.       w[44][i+3] = 1.0;
  157.       w[i+15][45] = -2.0;
  158.       w[i+24][45] = 1.0;
  159.       w[45][i+6] = 1.0;
  160.       w[9+4*i][46] = -2.0;
  161.       w[18+4*i][46] = 1.0;
  162.       w[46][4*i] = 1.0;
  163.       w[11+2*i][47] = -2.0;
  164.       w[20+2*i][47] = 1.0;
  165.       w[47][2+2*i] = 1.0;
  166.       w[9+3*i][48] = -2.0;
  167.       w[18+3*i][48] = 1.0;
  168.       w[48][3*i] = 1.0;
  169.       w[10+3*i][49] = -2.0;
  170.       w[19+3*i][49] = 1.0;
  171.       w[49][1+3*i] = 1.0;
  172.       w[11+3*i][50] = -2.0;
  173.       w[20+3*i][50] = 1.0;
  174.       w[50][2+3*i] = 1.0;
  175.    }
  176. /*   friendly singleton detectors */
  177.    for(i = 0; i < 3; i++)
  178.    {  w[i+9][51] = 1.0;
  179.       w[i+18][51] = -2.0;
  180.       w[51][i] = 2.0;
  181.       w[i+12][52] = 1.0;
  182.       w[i+21][52] = -2.0;
  183.       w[52][i+3] = 2.0;
  184.       w[i+15][53] = 1.0;
  185.       w[i+24][53] = -2.0;
  186.       w[53][i+6] = 2.0;
  187.       w[9+4*i][54] = 1.0;
  188.       w[18+4*i][54] = -2.0;
  189.       w[54][4*i] = 2.0;
  190.       w[11+2*i][55] = 1.0;
  191.       w[20+2*i][55] = -2.0;
  192.       w[55][2+2*i] = 2.0;
  193.       w[9+3*i][56] = 1.0;
  194.       w[18+3*i][56] = -2.0;
  195.       w[56][3*i] = 2.0;
  196.       w[10+3*i][57] = 1.0;
  197.       w[19+3*i][57] = -2.0;
  198.       w[57][1+3*i] = 2.0;
  199.       w[11+3*i][58] = 1.0;
  200.       w[20+3*i][58] = -2.0;
  201.       w[58][2+3*i] = 2.0;
  202.    }
  203. /*   enemy singleton detectors */
  204.    for(i = 0; i < 3; i++)
  205.    {  w[i+9][59] = -2.0;
  206.       w[i+18][59] = 1.0;
  207.       w[59][i] = 2.0;
  208.       w[i+12][60] = -2.0;
  209.       w[i+21][60] = 1.0;
  210.       w[60][i+3] = 2.0;
  211.       w[i+15][61] = -2.0;
  212.       w[i+24][61] = 1.0;
  213.       w[61][i+6] = 2.0;
  214.       w[9+4*i][62] = -2.0;
  215.       w[18+4*i][62] = 1.0;
  216.       w[62][4*i] = 2.0;
  217.       w[11+2*i][63] = -2.0;
  218.       w[20+2*i][63] = 1.0;
  219.       w[63][2+2*i] = 2.0;
  220.       w[9+3*i][64] = -2.0;
  221.       w[18+3*i][64] = 1.0;
  222.       w[64][3*i] = 2.0;
  223.       w[10+3*i][65] = -2.0;
  224.       w[19+3*i][65] = 1.0;
  225.       w[65][1+3*i] = 2.0;
  226.       w[11+3*i][66] = -2.0;
  227.       w[20+3*i][66] = 1.0;
  228.       w[66][2+3*i] = 2.0;
  229.    }
  230. /* biases */
  231.    for(i = 0; i < 9; i++)
  232.       bias[i] = 0.0625;
  233.    for(i = 0; i < 8; i++)
  234.    {  bias[i+27] = 0.5;
  235.       bias[i+35] = -1.5;
  236.       bias[i+43] = -1.5;
  237.       bias[i+51] = -0.5;
  238.       bias[i+59] = -0.5;
  239.     }
  240.     for(i = 0; i < N; i++)
  241.     {  bias[i] *= SCALE;
  242.        for(j = 0; j < N; j++)
  243.           w[i][j] *= SCALE;
  244.     }
  245. #ifdef DEBUG
  246.    for(i = 0; i < N; i++)
  247.    {
  248.       for(j = 0; j < N; j++)
  249.          printf("%2.0f",w[i][j]);
  250.       printf("%7.2f\n",bias[i]);
  251.    }
  252. #endif
  253. }
  254.  
  255. randint(n)
  256. int n;
  257. /* return a random integer in the range 0 to n-1 */
  258. {
  259.    return(rand() % n);
  260. }
  261.  
  262. #define MAXSIZE 5
  263. boxes(a,n)
  264. float a[];
  265. int n;
  266. /*    Draw boxes proportional to activation levels (a) ala Hinton diagrams.
  267.  *    If n equals N then draw all N boxes otherwise draw only the nth.
  268.  */
  269. {
  270.    int i,j,k,x,y,x0,y0;
  271.    int size,count;
  272.  
  273.    x0 = 5;
  274.    y0 = 40;
  275.    count = -1;
  276.    for(k = 0; k < 3; k++)
  277.    {  x = x0;
  278.       y = y0;
  279.       for(i = 0; i < 3; i++)
  280.       {  for(j = 0; j < 3; j++)
  281.          {  x += 12;
  282.             count++;
  283.             if(n == N || n == count)
  284.             {  size = a[count]*MAXSIZE;
  285.                _setcolor(0);
  286.                _rectangle(_GFILLINTERIOR,
  287.                x-MAXSIZE,y-MAXSIZE,x+MAXSIZE,y+MAXSIZE);
  288.                _setcolor(15);
  289.                _rectangle(_GBORDER,x-size,y-size,x+size,y+size);
  290.             }
  291.          }
  292.          x = x0;
  293.          y += 12;
  294.       }
  295.       x0 += 48;
  296.    }
  297.    y0 = 40;
  298.    for(k = 0; k < 5; k++)
  299.    {  x = x0;
  300.       y = y0;
  301.       for(i = 0; i < 3; i++)
  302.       {  for(j = 0; j < 3; j++)
  303.          {  x += 12;
  304.             if(i != 1 || j != 1)
  305.             {  count++;
  306.                if(n == N || n == count)
  307.                {  size = a[count]*MAXSIZE;
  308.                   _setcolor(0);
  309.                   _rectangle(_GFILLINTERIOR,
  310.                   x-MAXSIZE,y-MAXSIZE,x+MAXSIZE,y+MAXSIZE);
  311.                   _setcolor(15);
  312.                   _rectangle(_GBORDER,x-size,y-size,x+size,y+size);
  313.                }
  314.             }
  315.           }
  316.           x = x0;
  317.           y += 12;
  318.       }
  319.       x0 += 48;
  320.    }
  321. }
  322.  
  323. drawboard()
  324. {  static char board[5][6] = {32,179,32,179,32,0,
  325.                   196,197,196,197,196,0,
  326.                   32,179,32,179,32,0,
  327.                   196,197,196,197,196,0,
  328.                   32,179,32,179,32,0};
  329.    int i;
  330.    _clearscreen(_GCLEARSCREEN);
  331.    for(i = 0; i < 5; i++)
  332.    {  _settextposition(i+8,37);
  333.       _outtext(&board[i][0]);
  334.    }
  335.    _settextposition(2,2);
  336.    _outtext("move    x     o   empty   2x    2o    1x    1o");
  337.    _settextposition(19,5);
  338.    _outtext("Use arrow keys to move cursor.");
  339.    _settextposition(20,5);
  340.    _outtext("ENTER will change the marker under the cursor. x is program, o is opponent.");
  341.    _settextposition(21,5);
  342.    _outtext("ESCAPE will start network.");
  343.    _settextposition(22,5);
  344.    _outtext("After network is started, any key will stop.");
  345.    _settextposition(23,5);
  346.    _outtext("ESCAPE while network is running will exit program");
  347. }
  348.  
  349. putmarkers(b,x)
  350. float b[];          /*  board description vector for input to network */
  351. int x;              /*  location of programs new move */
  352. /*
  353.  *   puts x's and o's on the board
  354.  *   x is the programs marker,
  355.  *   o is the opponents marker
  356.  */
  357. {  int i,row,col;
  358.    static int board[9] = {0};
  359.    int c, c1;
  360. /*  place the programs new move on the board */
  361.    if(x > -1)
  362.    {  _settextposition(8+2*(x/3),37+2*(x%3));
  363.       _outtext("x");
  364.       board[x] = 1;
  365.    }
  366. /*  get the users input to the new board description */
  367.    row = 8;
  368.    col = 37;
  369.    i = 0;
  370.    _settextposition(row,col);
  371.    _displaycursor(_GCURSORON);
  372.    while((c = getch()) != 27)   /* continue until escape is hit */
  373.    {  switch(c)
  374.       {  case 13:        /*  enter key */
  375.          {  board[i] = (board[i]+1)%3;
  376.             if(board[i] == 0)
  377.               _outtext(" ");
  378.             else if(board[i] == 1)
  379.               _outtext("x");
  380.             else
  381.               _outtext("o");
  382.             _settextposition(row,col);
  383.             break;
  384.          }
  385.          case 0:
  386.          {  c1 = getch();
  387.             switch(c1)
  388.             {  case 72:      /*   up arrow */
  389.                {  if(row > 8)
  390.                   {  row -= 2;
  391.                      i -= 3;
  392.                      _settextposition(row,col);
  393.                      break;
  394.                   }
  395.                }
  396.                case 75:      /* left arrow */
  397.                {  if(col > 37)
  398.                   {  col -= 2;
  399.                      i--;
  400.                      _settextposition(row,col);
  401.                      break;
  402.                   }
  403.                }
  404.                case 77:      /* right arrow */
  405.                {  if(col < 41)
  406.                   {  col += 2;
  407.                      i++;
  408.                      _settextposition(row,col);
  409.                      break;
  410.                    }
  411.                 }
  412.                 case 80:      /* down arrow */
  413.                 {  if(row < 12)
  414.                    {  row += 2;
  415.                       i += 3;
  416.                       _settextposition(row,col);
  417.                       break;
  418.                    }
  419.                 }
  420.              }
  421.           }
  422.       }
  423.    }
  424.    _displaycursor(_GCURSOROFF);
  425.    for(i = 0; i < 9; i++)
  426.    {   switch(board[i])
  427.        {  case 0:
  428.           {  b[i] = 0.0;
  429.              b[i+9] = 0.0;
  430.              break;
  431.            }
  432.            case 1:
  433.            {  b[i] = 1.0;
  434.               b[i+9] = 0.0;
  435.               break;
  436.            }
  437.            case 2:
  438.            {  b[i] = 0.0;
  439.               b[i+9] = 1.0;
  440.               break;
  441.            }
  442.        }
  443.    }
  444. }
  445.        case 2:
  446.            {  b[i] = 0.0;
  447.               b[i+9] = 1.0;
  448.               break;
  449.            }
  450.       t n;
  451. /*    Draw boxes proportional to activation levels (a) ala Hinton diagrams.
  452.  *    If n equals N then draw all N boxes otherwise draw only the nth.
  453.  */
  454. {
  455.    int i,j,k,x,y,x0,y0;
  456.    int size,count;
  457.  
  458.    x0 = 5;
  459.    y0 = 40;
  460.    count = -1;
  461.    for(k = 0; k < 3; k++)
  462.    {  x = x0;
  463.       y = y0;
  464.       for(i = 0; i < 3; i++)
  465.       {  for(j = 0; j < 3; j++)
  466.          {  x += 12;
  467.             count++;
  468.             if(n == N || n == count)
  469.             {  size = a[count]*MAXSIZE;
  470.                _setcolor(0);
  471.                _rectangle(_GFILLINTERIOR,
  472.                x-MAXSIZE,y-MAXSIZE,x+MAXSIZE,y+MAXSIZE);
  473.                _setcolor(15);
  474.                _rectangle(_GBORDER,x-size,y-size,x+size,y+size);
  475.             }
  476.          }
  477.          x = x0;
  478.